package union_find

//  UF第一版：直接指向自己的父亲集合,是一个高度为2的树，很扁平
type UnionFindV1 struct {
	id []int
}

func NewUnionFindV1(size int) *UnionFindV1 {
	id := make([]int, size)
	for i := 0; i < len(id); i++ {
		id[i] = i
	}
	return &UnionFindV1{id}
}

func (u *UnionFindV1) find(p int) int {
	if p < 0 || p >= len(u.id) {
		panic("element out of range")
	}
	return u.id[p]
}

func (u *UnionFindV1) Size() int {
	return len(u.id)
}

func (u *UnionFindV1) IsConnected(p int, q int) bool {
	return u.find(p) == u.find(q)
}

func (u *UnionFindV1) Union(p int, q int) {
	pId := u.find(p)
	qId := u.find(q)

	if pId == qId {
		return
	}

	for i := 0; i < len(u.id); i++ {
		if u.id[i] == pId {
			u.id[i] = qId
		}
	}
}
